import math

from lazyselect import median

from math_utils import argmin, argmax
from two_d_utils import counterclockwise, vector, angle, cross_product
from utils import merged_ordered


def merge(ch_l, ch_r):
    base = ch_l[0]

    end_a = argmin(ch_r, key=lambda x: angle((0, -1), vector(base, x)))
    end_b = argmax(ch_r, key=lambda x: angle((0, -1), vector(base, x)))
    ch_r_r = []
    if len(ch_r) == 2:
        ch_r_r = [ch_r[end_a], ch_r[end_b]]
    else:
        if end_b > end_a:
            num = end_b - end_a + 1
        else:
            num = len(ch_r) - end_a + end_b + 1

        for i in range(num):
            ch_r_r.append(ch_r[(end_a + i) % len(ch_r)])

    return merged_ordered(ch_l, ch_r_r, key=lambda x: 0.0 if x == base else angle((0, -1), vector(base, x)))


def _convex_hull_d_c(points):

    # 可能会有2个点的情况，不会有1个点的情况
    # 因为： 3个点会直接返回，因此继续递归最少会有4个点，现在考虑4个点的情况
    # 4个点的中位数是第2个点，所以左部分和右部分都有2个点（中位数本身会被分配到左部分），不会出现1个点的情况
    # 多于4个点递归更不可能出现1个点的情况
    if len(points) < 3:
        if points[0][0] > points[1][0]:
            points.reverse()
        return points
    elif len(points) == 3:
        left_most = argmin(points, key=lambda x: x[0])
        points[0], points[left_most] = points[left_most], points[0]
        return list(counterclockwise(points))
    else:
        m = median(points, key=lambda x: x[0])

        # 根据x中位数将点分为左右两部分
        left, right = [], []
        for point in points:
            if point[0] <= m[0]:
                left.append(point)
            else:
                right.append(point)

        # 分治
        ch_l = _convex_hull_d_c(left)
        ch_r = _convex_hull_d_c(right)

        # merge
        merged_points = merge(ch_l, ch_r)
        # graham scan
        stack = [merged_points[0], merged_points[1]]
        for i in range(2, len(merged_points)):
            next_point = merged_points[i]

            # 如果向外转弯，则出栈栈顶点
            while cross_product(vector(stack[-2], stack[-1]), vector(stack[-1], next_point)) < 0:
                stack.pop()
            # 新顶点入栈
            stack.append(next_point)
        return stack
        

def convex_hull_d_c(points):
    return _convex_hull_d_c(points)
